package org.example.linkedList;

import java.util.Arrays;

/**
 * @Auther: wangbw @Date:2020/12/22 @Description: org.example.linkedList @version: 1.0
 */
public class CountingSort {
    public static void main(String[] args) {
        int[] A = countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});
        print(A);
    }

    public static int[] countingSort(int[] A) {
        if (A == null && A.length <= 1)
            return A;
        int max = A[0], min = A[0];
        for (int i = 0; i < A.length; i++) {
            if (A[i] > max) max = A[i];
            if (A[i] < min) min = A[i];
        }
        int[] C = new int[max - min + 1];
        for (int i = 0; i < A.length; i++) C[A[i] - min]++;
        for (int i = 1; i < C.length; i++) C[i] = C[i] + C[i - 1];
        int[] B = new int[A.length];
        for (int i = A.length - 1; i >= 0; i--) B[--C[A[i] - min]] = A[i];
        return B;
    }

    private static void print(int[] arr) {
        System.out.println("result:" + Arrays.toString(arr));
    }
}
